package com.algorithm.detectCycle;

import com.algorithm.Common.LinkedNode;
import com.algorithm.Common.LinkedUtils;

public class AlMain {
    public static void main(String[] args) {
        int[] arr = new int[]{0,1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        LinkedNode head = LinkedUtils.create(arr);
        LinkedNode p1 = head;
        LinkedNode p2 = head;
        //下面四行去掉就是链表无环，输出值就是false
        while (p1.getNext() != null) {
            p1 = p1.getNext();
        }
        for (int i = 0; i < 5; i++) {
            p2 = p2.getNext();
        }

        p1.setNext(p2);
        System.out.println(detectCycle(head).getData());
    }

    public static LinkedNode detectCycle(LinkedNode head) {
        LinkedNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            slow = slow.getNext();
            //第一次相遇
            if (slow == fast) {
                break;
            }
            if (fast == null || fast.getNext() == null) {
                // fast 遇到空指针说明没有环
                return null;
            }
        }
        slow = head;
//        第二次相遇
        while (slow != fast) {
            slow = slow.getNext();
            fast = fast.getNext();
        }
        return slow;
    }
}
